//package test1;
//
//import java.util.Arrays;
//import java.util.Stack;
//
//public class Test6 {
//    public static void main(String[] args) {
//        int[] nums = new int[]{1, 5, 2, 5, 2, 5, 3, 4, 8, 9};
//        int[] arr = qucik_sort(nums);
//        for (int i : arr) {
//            System.out.print(i + " ");
//        }
//    }
//
//    //方式一非递归实现
//    private static int[] qucik_sort(int[] nums) {
//        Stack stack = new Stack();
//        while (stack != null) {
//            int right =
//        }
//    }
//
//    private int one_sort(int[] nums, int begin, int end) {
//        int key = begin;
//        int left = begin;
//        int right = end;
//
//        while (left < right) {
//            while (left < right && nums[right] >= nums[key]) {
//                right--;
//            }
//            while (left < right && nums[left] <= nums[key]) {
//                left++;
//            }
//            if (left < right) {
//                swap(nums, left, right);
//            }
//        }
//        int meet = left;
//        swap(nums, meet, key);
//        return meet;
//    }
//
//    private void swap(int[] nums, int left, int right) {
//        int tmp = nums[left];
//        nums[left] = nums[right];
//        nums[right] = tmp;
//    }
////
////    //方法三 前后指针法
////    private static int[] qucik_sort(int[] nums, int begin, int end) {
////        if (begin > end) {
////            return nums;
////        }
////        int pre = begin;
////        int cur = pre + 1;
////        int key = begin;
////
////        while (cur <= end) {
////            if (nums[cur] < nums[key] && ++pre != cur) {
////                swap(nums, pre, cur);
////            }
////            cur++;
////        }
////
////        int meet = pre;
////        swap(nums, meet, key);
////        qucik_sort(nums, begin, meet - 1);
////        qucik_sort(nums, meet + 1, end);
////        return nums;
////    }
////
////    private static void swap(int[] nums, int pre, int cur) {
////        int tmp = nums[pre];
////        nums[pre] = nums[cur];
////        nums[cur] = tmp;
////    }
//
////    private static void swap(int[] nums, int meet, int key) {
////        int tmp = nums[meet];
////        nums[meet] = nums[key];
////        nums[key] = tmp;
////    }
//
//    //    //方法一hoare法
////    private static int[] qucik_sort(int[] nums, int begin, int end) {
////        if (begin > end) {
////            return nums;
////        }
////        int left = begin;
////        int right = end;
////        int key = left;
////        while (left < right) {
////            while (left < right && nums[right] >= nums[key]) {
////                right--;
////            }
////            while (left < right && nums[left] <= nums[key]) {
////                left++;
////            }
////            if (left < right) {
////                swap(nums, left, right);
////            }
////        }
////        int meet = left;
////        swap(nums, meet, key);
////        qucik_sort(nums, begin, meet - 1);
////        qucik_sort(nums, meet + 1, end);
////        return nums;
////    }
////    //方法二 挖坑法
////    private static int[] qucik_sort(int[] nums, int begin, int end) {
////        if (begin > end) {
////            return nums;
////        }
////        int left = begin;
////        int right = end;
////        int key = nums[left];
////
////        while (left < right) {
////            while (left < right && nums[right] >= key) {
////                right--;
////            }
////            nums[left] = nums[right];
////            while (left < right && nums[left] <= key) {
////                left++;
////            }
////            nums[right] = nums[left];
////        }
////        int meet = left;
////        nums[left] = key;
////        qucik_sort(nums, begin, meet - 1);
////        qucik_sort(nums, meet + 1, end);
////        return nums;
////    }
//
//}
